package net.fonline.apps.pathfinder;

import net.fonline.apps.LineTowerWars;

/**
 * This class solves a maze by using a*-algorithm
 * Initially written by Scaatis. Removed a few logical errors and corrected to JavaME-generic by Michael.
 * @author Scaatis, Michael
 */
public class Maze {

    public int rows;
    public int columns;
    public Square[][] elements;
    public int goalX;
    public int goalY;
    public int startX;
    public int startY;

    public Maze(int rows, int columns) {
        this.rows = rows;
        this.columns = columns;
        elements = new Square[rows][columns];
        init();
    }

    private void init() {
        createSquares();
        setStartAndGoal();
    }

    private void createSquares() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                elements[i][j] = new Square(i, j);
            }
        }
    }

    private void setStartAndGoal() {
        goalX = (elements.length - 1) / 2;
        goalY = (elements[goalX].length - 1);
        elements[goalX][goalY].passable = true;
        startX = (elements.length - 1) / 2;
        startY = 0;
        elements[startX][startY].passable = true;
    }

    public void draw() {
        LineTowerWars.ec.map.entities[0][0].useForPath();
        for (int y = 0; y < columns; y++) {
            for (int x = 0; x < rows; x++) {
                if (elements[x][y].path) {
                    LineTowerWars.ec.map.entities[x][y].useForPath();
                } else {
                    LineTowerWars.ec.map.entities[x][y].resetPath();
                }
            }
        }
        LineTowerWars.ec.map.entities[4][0].useForPath();
        LineTowerWars.ec.map.entities[4][LineTowerWars.ec.map.entities[0].length - 1].useForPath();
    }

    /**
     * Use the A* Algorithm to find the shortest path through the labyrinth.
     */
    public Node findBestPath() {
        //The set of Nodes yet to be considered
        ArrayList openset = new ArrayList();

        //The set of Nodes that have already been considered
        ArrayList closedset = new ArrayList();

        //When starting, the starting Node is the only one in the open set.
        openset.add(new Node(elements[startX][startY], null));

        //To save time, we save the goal square now.
        Square goal = elements[goalX][goalY];

        //DEGUB: int i=1;
        while (openset.size() > 0) {
            //DEBUG: System.out.println(i);
            //DEBUG: i++;
            // Find the Node with the lowest traversal cost, this is our
            // current Node
            Node lowest = getLowestFNode(openset, goal);

            // Drop it from the open set and add it to the closed set.
            closedset.add(lowest);
            openset.remove(lowest);

            //Have we arrived at the goal?
            if (lowest.square.x == goal.x && lowest.square.y == goal.y) {
                // We break out of the loop, the target Node is now the last one
                // added to the closed set.
                break;
            }

            //Find all passable Nodes adjacent to the current node, as children
            //of the current Node
            ArrayList adjacencies = getAdjacentNodes(lowest);

            Node adj = null;
            for (int i = 0; i < adjacencies.size(); i++) {
                adj = adjacencies.get(i);
                // If the Node is not in the open set, add it.
                Node sim = getSimilarNode(openset, adj);
                if (sim == null) {
                    // Ignore Nodes that are in the closed set already
                    if (getSimilarNode(closedset, adj) == null) {
                        openset.add(adj);
                    }
                } else {
                    // If the Node is in the current set, see whether going to
                    // that Node via the current Node is cheaper than going there
                    // via the Node it was child of before
                    int gThis = adj.getParentCost();
                    int gOther = sim.getParentCost();
                    if (gThis < gOther) {

                        // If so, change it's parent to the current Node
                        sim.parent = adj.parent;
                    } // If not, ignore the Node.
                }
            }
        }

        // At this point, we either have reached the target Node or the open set
        // is empty, which means that there is no path. If there is a path, the
        // target Node is the last one in the closed set.
        Node target = closedset.get(closedset.size() - 1);

        if (target.square.x == goal.x && target.square.y == goal.y) {
            return target;
        } else {
            return null;
        }
    }

    /**
     * Get the passable squares adjacent to this one and return them as child Nodes
     * of the given Node.
     * @param start
     * @return 
     */
    public ArrayList getAdjacentNodes(Node s) {
        ArrayList res = new ArrayList();

        Square start = s.square;

        if ((start.x - 1 >= 0) && elements[start.x - 1][start.y].passable) {
            res.add(new Node(elements[start.x - 1][start.y], s));
        }
        if ((start.x + 1 < elements.length) && elements[start.x + 1][start.y].passable) {
            res.add(new Node(elements[start.x + 1][start.y], s));
        }
        if ((start.y - 1 >= 0) && elements[start.x][start.y - 1].passable) {
            res.add(new Node(elements[start.x][start.y - 1], s));
        }
        if ((start.y + 1 < elements[start.x].length) && elements[start.x][start.y + 1].passable) {
            res.add(new Node(elements[start.x][start.y + 1], s));
        }
        return res;
    }

    /**
     * Find the Node with the lowest F-Score / TraversalCost and return it.
     * @param set
     * @param goal
     * @return 
     */
    private Node getLowestFNode(ArrayList set, Square goal) {
        int lowestScore = -1;
        int lowestIndex = -1;
        for (int i = 0; i < set.size(); i++) {
            if (lowestScore == -1) {
                lowestScore = set.get(i).getTraversalCost(goal);
                lowestIndex = i;
            } else {
                int f = set.get(i).getTraversalCost(goal);
                if (f <= lowestScore) {
                    lowestScore = f;
                    lowestIndex = i;
                }
            }
        }
        return set.get(lowestIndex);
    }

    /**
     * Check to see if the list already contains a Node associated with the same
     * Square and if so, return it.
     * @param openset
     * @return 
     */
    private Node getSimilarNode(ArrayList set, Node n) {
        for (int i = 0; i < set.size(); i++) {
            Node e = set.get(i);
            if (e.square.x == n.square.x && e.square.y == n.square.y) {
                return e;
            }
        }
        return null;
    }

    public void solve() {
        LineTowerWars.ec.cheatbot.cheat = true;
        Node target = this.findBestPath();
        ArrayList al = new ArrayList();
        if (target != null) {
            if (target.parent != null) {
                Node par = target.parent;
                while (par.parent != null) {
                    par.square.path = true;
                    al.add(par);
                    par = par.parent;
                }
                this.draw();
                LineTowerWars.ec.cheatbot.cheat = false;
                LineTowerWars.ec.map.current_path = al;
            }
        } else {
            this.draw();
            LineTowerWars.ec.cheatbot.cheat = true;
        }
    }
}
